package leetcode329周赛;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/22 13:26
 */
public class leetcode6299拆分数组的最小代价 {



/*
  暴力递归
   这个暴力递归
   还是 有些讲究的
   还是 让我 对 dp 有了 一个更深刻的理解
 */
    public static int recursion(int index,int[] nums,int k){
        if(index == nums.length){
            return 0;
        }

        int ans = Integer.MAX_VALUE;
        int[] map = new int[nums.length];
        int sum = 0;
        for(int i = index;i < nums.length;i++){
            map[nums[i]] ++;
            sum += map[nums[i]] == 1 ? 0 : map[nums[i]] == 2 ? 2 : 1;
            ans = Math.min(ans,recursion(i + 1,nums,k) + sum + k);
        }
        return ans;
    }


    // dp  AC
    public int dp(int[] nums,int k){
        int[] dp = new int[nums.length + 1];
        for(int index = nums.length - 1;index >= 0;index--){
            int ans = Integer.MAX_VALUE;
            int[] map = new int[nums.length];
            int sum = 0;
            for(int i = index;i < nums.length;i++){
                map[nums[i]] ++;
                sum += map[nums[i]] == 1 ? 0 : map[nums[i]] == 2 ? 2 : 1;
                ans = Math.min(ans,dp[i + 1] + sum + k);
            }
            dp[index] = ans;
        }
        return dp[0];
    }




    public static void main(String[] args) {
        int[] nums = {1,2,1,2,1};
        int k = 5;
        System.out.println(recursion(0,nums,k));
    }
}
